struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
//寻找二叉树两个节点的最近公共祖先
//设两个目标节点p,q
//普通二叉树，一个节点的左子树出现p,右子树出现q，那么这个节点就是他们的公共祖先

//使用后序遍历回溯（自下而上搜索）来寻找
//逻辑是如果左边找到了，右边没找到，就返回左边的返回值。反之一样
//这样就可以把找到的公共节点传递到根节点最后返回（因为无论如何都要遍历整棵树）

//递归法
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root==p||root==q||!root) return root;
    TreeNode* left=lowestCommonAncestor(root->left,p,q);    //左
    TreeNode* right=lowestCommonAncestor(root->right,p,q);  //右
    //中
    if(right&&left) return root;

    //最后传递到根节点的逻辑
    if(!right&&left) return left;
    else if(!left&&right) return right;
    else return nullptr;
}


//若是搜索二叉树，只需要寻找值介于两个目标节点之间的就可以
//可以采用任何遍历方法
//层序遍历
#include <queue>
using std::queue;
TreeNode* lowestCommonAncestor_(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(!root) return nullptr;
    queue<TreeNode*> que;
    que.push(root);
    int large=p->val>q->val? p->val:q->val;
    int small=p->val>q->val? q->val:p->val;
    while(!que.empty()){
        TreeNode* node=que.front();
        que.pop();
        if(small<=node->val&&large>=node->val)  return node;

        if(node->left) que.push(node->left);
        if(node->right) que.push(node->right);
    }

    return nullptr;
}

//根据搜索二叉树的特点进行搜索
TreeNode* _lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(!root) return nullptr;
    while(root){
        if(root->val>p->val&&root->val>q->val) root=root->left;
        else if(root->val<p->val&&root->val<q->val) root=root->right;
        else return root;
    }
    return nullptr;
}

//递归
//寻找思路和迭代相似
TreeNode* traversal(TreeNode* cur,TreeNode* p,TreeNode* q){
    if(!cur) return nullptr;
    //向左找
    if(cur->val>p->val&&cur->val>q->val) {
        TreeNode* left=traversal(cur->left,p,q);
        if(left) return left;
    }
    //向右找
    if(cur->val<p->val&&cur->val<q->val) {
        TreeNode* right=traversal(cur->right,p,q);
        if(right) return right;
    }
    //寻找到公共祖先
    return cur;
}
TreeNode* __lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    return traversal(root,p,q);
}